package pers.qianyu.month_202101.date_20210116;

import pers.qianyu.util.model.*;

/**
 * 19. 删除链表的倒数第N个节点
 * https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
 *
 * @author mizzle rain
 * @date 2021-01-16 22:42
 */
public class RemoveNthFromEnd {
    // 虚拟头结点 + 双指针
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        ListNode root = new ListNode();
        root.next = head;
        head = root;
        ListNode left = head, right = head;
        while (n-- > 0) right = right.next;
        while (right.next != null) {
            right = right.next;
            left = left.next;
        }
        ListNode delete = left.next;
        left.next = left.next.next;
        delete.next = null;
        return head.next;
    }
}
